package com.cat.DataStructure04;


import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
 * @create 2025/11/24 10:37
 * @since JDK17
 */

public class Solution02 {
    static int MAXN = 32;
    static int[][][] dp = new int[MAXN][2][2];
    static int dfs(int num, int len, int pre, int free) {
        if (len == -1) {
            return 1;
        }
        if (dp[len][pre][free] != -1) {
            return dp[len][pre][free];
        }
        int ans = 0;
        if (free == 0) {
            if ((1 << len & num) != 0) {    // 该位置是一
                if (pre == 0) {
                    ans += dfs(num, len - 1, 1, free);
                }
                ans += dfs(num, len - 1, 0, 1);
            } else {
                ans += dfs(num, len - 1, 0, free);
            }
        } else {
            if (pre == 0) {
                ans += dfs(num, len - 1, 1, free);
            }
            ans += dfs(num, len - 1, 0, free);
        }

        dp[len][pre][free] = ans;
        return ans;
    }

    public int findIntegers(int n) {
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < 2; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return dfs(n, 31, 0, 0);
    }
}
